package Tree;

import org.w3c.dom.Node;

import java.awt.image.renderable.RenderableImage;

public class BinarySearchTree{
    static class Node{
        public Node left;
        public int val;
        public Node right;
        public Node(int val){
            this.val  = val;
        }

    }

    public Node root = null;
    public boolean search(int val){
        Node cur = root;
        while(cur != null){
            if(val > cur.val){
                cur = cur.right;
            }else if(val < cur.val){
                cur = cur.left;
            }else{
                return true;
            }
        }
        return false;
    }

    public boolean  insert(int val){
        Node cur = root;
        Node node = new Node(val);
        Node parent = null;
        if(cur == null){
            root = node;
            return true;
        }
        while(cur != null){
            if(val > cur.val){
                parent = cur;
                cur = cur.right;
            }else if(val < cur.val){
                parent = cur;
                cur = cur.left;
            }else{
                return false;
            }
        }

        if(val > parent.val){
            parent.right = node;
        }else{
            parent.left = node;
        }
        return true;
    }

    public boolean remove(int val){
        Node cur =root;
        Node node = new Node(val);
        Node parent = null;
        while(cur != null){
            if(val > cur.val){
                parent = cur;
                cur = cur.right;
            }else if(val < cur.val){
                parent = cur;
                cur = cur.left;
            }else{
                break;
            }
        }

        if(cur == null){
           return false;
        }

        if(cur.left == null && cur.right == null){
            if(cur == root){
                root = null;
            }else if(cur == parent.left){
                parent.left = null;
            }else{
                parent.right = null;
            }
        }else if(cur.left == null || cur.right == null){
            Node child = (parent.left != null)? parent.left: parent.right;
            if(cur == root){
                root = child;
            }else if(cur == parent.left){
                parent.left = child;
            }else{
                parent.right = child;
            }
        }else{
            Node min = findMin(cur.right);
            cur.val = min.val;
            remove(min.val);
        }


        return true;
    }
    public Node findMin(Node node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
}